package com.yc.algorithm.leetcode.singleList;

import java.util.List;

/**
 * 写⼀个算法，合并2个有序的单链表。⽐如：
 * Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
 * Author:陈圆(chenyuan@bosssoft.com.cn) <br>
 * Date:2020/9/2
 */
public class ListNode {
    public static void main(String[] args) {
        ListNode list1 = new ListNode();
        list1.addNode(new Node(1));
        list1.addNode(new Node(2));
        list1.addNode(new Node(4));
//        list1.listNode();

        ListNode list2 = new ListNode();
        list2.addNode(new Node(1));
        list2.addNode(new Node(3));
        list2.addNode(new Node(4));
//        list2.listNode();

//        ListNode listNode = list1.mergeListNode(list2);
//        listNode.listNode();

        Node node = list2.reverseNode(list2.head);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }


    }

    private Node head ;


    /**
     * 链表反转
     */
    public Node reverseNode(Node node) {
        Node pre = null;
        Node next = null;
        while (node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

    /**
     * 单链表排序
     */
    public Node sortNode(Node node){
        // 定义 i 和 j  j = i + 1
        // 获取基准值 val
        // 判断node.j 是否大于 val

        return null;
    }

    /**
     * 单链表排序
     */
    public void sortLinkedList(List<Integer> list){

        sortLinkedList(list, 0, list.size() -1);
    }
    public void sortLinkedList(List<Integer> list, int left, int right) {
        if (left < right) {
            int i = left;
            int j = i + 1;
            int val = list.get(i);

            while(j <= right) {
                // 大条件，j不能超过链表长度
                while(j <= right && list.get(j) >= val) {
                    // 如果j指向的值大于基准值，则 j向右移动
                    j ++;
                }
                // 否则，交换i 和 j
                if (j <= right) {
                    i++;
                    swap(list, i, j);
                    j++;
                }
            }
            // 最后交换i位置的值和基准值
            swap(list, left, i);
            sortLinkedList(list, left, i -1);
            sortLinkedList(list, i + 1, right);
        }
    }

    private void swap(List<Integer> list, int i, int j){
        int iVal = list.get(i);
        list.set(i, list.get(j));
        list.set(j, iVal);
    }





    /***
     * 合并list,
     * 1,将ListNode转成数组合并
     * 2，排序
     * 3.添加
     * Date:2020/9/2
     * @param list2
     * @return com.yc.algorithm.leetcode.singleList.ListNode
     */
    public ListNode mergeListNode(ListNode list2) {
        ListNode result = new ListNode();
        ListNode list1 = this;
//        if (list1 == null) {
//            return list2;
//        }
        if (list2 == null) {
            return list1;
        }
        int[] nodes1 = list1.ListNodeToArr();
        int[] nodes2 = list2.ListNodeToArr();

        // 合并数组
        int[] nodes = new int[nodes1.length + nodes2.length];
        for (int i=0; i<nodes1.length; i++) {
            nodes[i] = nodes1[i];
        }
        for (int i=0; i<nodes2.length; i++) {
            nodes[nodes1.length+i] = nodes2[i];
        }
        // 冒泡排序
        int tmp;
        for (int i=0; i<nodes.length-1; i++) {
            for (int j=0; j<nodes.length-1-i; j++) {
                if (nodes[j] > nodes[j + 1]) {
                    tmp = nodes[j];
                    nodes[j] = nodes[j + 1];
                    nodes[j + 1] = tmp;
                }
            }
        }

        for (int i=0; i<nodes.length; i++) {
            result.addNode(new Node(nodes[i]));
        }

        return result;
    }

    public int[] ListNodeToArr() {
        int size = 0;
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            size++;
            temp = temp.next;
        }
        int[] nodeArr = new int[size];
        Node n = head;
        for (int i=0;  i<size; i++) {
            nodeArr[i] = n.next.val;
            n = n.next;
        }
        return nodeArr;

    }

    public void addNode(Node e) {
        Node node = head;
        while (true) {
            if (node.next == null) {
                break ;
            }
            node = node.next;
        }
        node.next = e;
    }




    public void listNode() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node next = head.next;
        while (true) {
            if (next == null) {
                break;
            }
            System.out.println(next);
            next = next.next;
        }
    }

    static class Node {
        public int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "val=" + val ;
        }
    }
}
